
// 移除链表元素
public class removeElement {
  public static void main(String[] args) {
    // 构建测试链表 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6
    ListNode node7 = new ListNode(6);
    ListNode node6 = new ListNode(5, node7);
    ListNode node5 = new ListNode(4, node6);
    ListNode node4 = new ListNode(3, node5);
    ListNode node3 = new ListNode(6, node4);
    ListNode node2 = new ListNode(2, node3);
    ListNode head = new ListNode(1, node2);
    // ListNode node4 = new ListNode(7);
    // ListNode node3 = new ListNode(7, node4);
    // ListNode node2 = new ListNode(7, node3);
    // ListNode head = new ListNode(7, node2);
    // 调用移除方法，val = 6
    ListNode result = new removeElement().removeElements(head, 6);

    // 验证结果是否为 [1,2,3,4,5]
    System.out.println("\n输出结果：" + listToString(result));
    System.out.println("预期结果：1 2 3 4 5");
  }

  // 辅助方法：将链表转换为字符串
  private static String listToString(ListNode head) {
    StringBuilder sb = new StringBuilder();
    while (head != null) {
      sb.append(head.val).append(" ");
      head = head.next;
    }
    return sb.toString().trim();
  }

  /**
   * 第一种方法：直接用原来的链表删除
   * 1.创建链表的节点
   * 2.需要区分移除的是否为头节点
   * 3.如果是头结点的话，就需要将头节点向后移动一位
   *    如果是其他节点，则先从头节点开始，判断下一节点是否为target
   *    如果是target的话，则将当前节点指向当前节点的next
   * 4.返回head
   * 
   * 时间复杂度O(n)
   * 空间复杂度O(1)
   */
  // public ListNode removeElements(ListNode head, int target) {
  // // 如果target是头节点的话，则向后移动一位
  // // 这里使用while而不是if，是因为if只判断一次
  // // 如果所有节点的值都相等，判断一次后就会漏删头节点
  // while (head != null && head.val == target) {
  // head = head.next;
  // }

  // 需要定义一个临时指针来操作链表，防止头节点的值更改，无法返回最新的头节点
  // ListNode cur = head;
  // // 如果是其他节点的话，则从头节点开始，判断下一节点是否为target
  // while (cur != null && cur.next != null) {
  // // 如果是的话，当前指针的下节点指向下下个节点
  // if (cur.next.val == target) {
  // cur.next = cur.next.next;
  // } else {
  // // 如果不是的话，则当前节点向后移动
  // cur = cur.next;
  // }
  // }

  // return head;
  // }

  /**
   * 第二种方法：设置一个虚拟节点
   * 1.创建链表的节点
   * 2.设置一个虚拟节点dumy，下一节点是头节点
   * 3.用统一的逻辑处理节点操作
   * 4.返回dumy.next
   * 
   * 时间复杂度O(n)
   * 空间复杂度O(1)
   */
  // public ListNode removeElements(ListNode head, int target) {
  // ListNode dumy = new ListNode();
  // dumy.next = head;
  // ListNode cur = dumy;
  // while (cur != null && cur.next != null) {
  // if (cur.next.val == target) {
  // cur.next = cur.next.next;
  // } else {
  // cur = cur.next;
  // }
  // }
  // return dumy.next;
  // }

  /**
   * 第三种方法：递归删除
   * 1.创建链表的节点
   * 2.基础情况：对于空链表，不需要移除元素
   * 3.判断头节点是否为target，如果移除头节点，返回头节点后续节点递归的结果
   * 4.如果不是，则返回的结果是头节点与头节点后续节点递归的新链表拼接的结果
   * 
   * 时间复杂度O(n)
   * 空间复杂度O(n)
   */
  public ListNode removeElements(ListNode head, int target) {
    if (head == null) {
      return head;
    }

    // 假设 removeElements() 返回后面完整的已经去掉val节点的子链表
    // 在当前递归层用当前节点接住后面的子链表
    // 随后判断当前层的node是否需要被删除，如果是，就返回
    // 也可以先判断是否需要删除当前node，但是这样条件语句会比较不好想
    head.next = removeElements(head.next, target);
    if (head.val == target) {
      return head.next;
    }
    return head;

    // 实际上就是还原一个从尾部开始重新构建链表的过程
  }

  // 定义一个指针的节点
  public static class ListNode {
    // 节点的值
    int val;
    // 下一个节点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {

    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
      this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }
}
